package com.bm;

/**
 * Description: BM57 岛屿数量
 * 做法，把所有相邻1的改成从2开始的字符，那么遍历完后，同一个岛屿字符一样，不同岛屿字符不一样，且相差1，那么结果就是最后的岛屿字符-初始岛屿字符
 *
 * @author weiruibai.vendor
 * Date: 2022/9/26 09:34
 */
public class BM57 {

    public static void main(String[] args) {
        System.out.println((int) '2');
        System.out.println((int) '3');


        char[][] grid = new char[][]{
                {'1', '1', '0', '0', '0'},
                {'0', '1', '1', '1', '1'},
                {'0', '0', '0', '1', '1'},
                {'0', '0', '0', '0', '0'},
                {'0', '0', '1', '1', '1'}};
        BM57 bm57 = new BM57();
        System.out.println(bm57.solve(grid));
    }

    public int solve(char[][] grid) {
        int N = grid.length;
        int M = grid[0].length;
        char state = '2';
        boolean[][] visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == '1') {
                    doProcess(grid, i, j, state, visited);
                    state = (char) ((int) state + 1);
                }
            }
        }
        return state - '2';
    }

    private void doProcess(char[][] grid, int i, int j, char state, boolean[][] visited) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
            return;
        }
        if (visited[i][j] || grid[i][j] == '0') {
            return;
        }
        visited[i][j] = true;
        grid[i][j] = state;
        // 上
        doProcess(grid, i - 1, j, state, visited);
        // 下
        doProcess(grid, i + 1, j, state, visited);
        // 左
        doProcess(grid, i, j - 1, state, visited);
        // 右
        doProcess(grid, i, j + 1, state, visited);
    }


}
